#include <iostream>
#include <string>

using namespace std;

class Solution {
public:
  int strStr(string haystack, string needle) {
    // kmp algo
    int mi = 0;
    int si = 0;

    int visit = 0;
    while (mi < haystack.size() && si < needle.size()) {
      char mc = haystack[mi];
      char sc = needle[si];

      if (mc == sc) {
        mi++;
        si++;
        continue;
      }

      visit++;
      si = 0;
      mi = visit;
    }
    if (si == needle.size()) {
      return visit;
    }
    return -1;
  }
};

void testcase02() {
  printf("\n%s Running\n", __FUNCTION__);
  string input1 = "leetcode";
  string input2 = "leeto";
  int want = -1;
  Solution so;
  int got = so.strStr(input1, input2);
  if (got != want) {
    printf("failed! want:%d, but got:%d\n", want, got);
  }else {
    printf("success!\n");
  }
}
void testcase01() {
  printf("\n%s Running\n", __FUNCTION__);
  string input1 = "sadbutsad";
  string input2 = "sad";
  int want = 0;
  Solution so;
  int got = so.strStr(input1, input2);
  if (got != want) {
    printf("failed! want:%d, but got:%d\n", want, got);
  }else {
    printf("success!\n");
  }
}

int main() {
  testcase01();
  testcase02();
  return 0;
}
